#pragma once

#include <algorithm>
#include <vector>

namespace solution_045
{

class Solution
{
public:
    int jump(std::vector<int>& nums)
    {
        auto min_step = std::vector(nums.size(), 0);
        for (size_t i = 0, untouched = 1; untouched < nums.size(); ++i) {
            auto current_step = min_step.at(i);
            auto max_step = nums.at(i);
            auto next_untouched = std::min(i + max_step + 1, nums.size());
            if (next_untouched >= untouched) {
                std::fill(min_step.begin() + untouched,
                          min_step.begin() + next_untouched,
                          current_step + 1);
                untouched = next_untouched;
            }
        }
        return min_step.back();
    }
};

}  /* namespace solution_045 */
